1. Field of the Invention
The present invention relates to an adaptive execution method of a parallel program for a multithreaded processor-based parallel system, and more particularly, to a method of executing a program using an adaptive execution method after predicting the performance of a parallel loop using a performance prediction model when compiling or executing, in order to reflect structural characteristics of a system.
2. Discussion of Related Art
A parallel processor system having m processors should theoretically show an m-fold improvement in execution speed compared to a single processor system. However, in actuality, it cannot achieve such an improvement in performance due to overhead caused by parallel execution, lack of parallelism, and difficulty in parallel programming. Of the above problems, difficulty in parallel programming can be solved by a skilled programming expert, but it requires a considerable amount of time and money to train and use such an expert. In order to solve the problem, a parallelizing compiler has been being developed which parallelizes sequential programs made by the existing sequential programming technique by using a compiler technique.
In order to improve the performance of the parallel program, various optimizing techniques have been applied to the parallelizing compiler. A stumbling block in optimization is that information about a computer in which the parallel program is to be executed, or information about data to be input when the parallel program is executed, is not transferred to the parallelizing compiler. That is, the performance of an algorithm depends on the computer in which it is executed, but it is difficult to get the information during a compiling time. Research has been conducted into improving the performance by optimizing the parallel program or making the parallel program adaptive to an execution environment when the information about the computer in which the parallel program is to be executed or the information about the input data is provided completely, i.e., when the parallel program is executed. The present invention pertains to this field of research.
The present invention relates to a multithreaded processor-based parallel system which is rapidly beginning to dominate the server market. The parallel system is based on a multithreaded processor which entirely or partially shares a cache such as a simultaneous multi-threading (SMT) or a chip multi-processor (CMP). In such a parallel system, it is very difficult to obtain desired performance by applying the optimizing technique used in the existing parallelizing compiler because it does not reflect structural characteristics of the processor.
A prior article, entitled: “Adaptively increasing performance and scalability of automatically parallelized programs”, Jaejin Lee, H. D. K. Moonesinghe, Lecture Notes in Computer Science, vol. 2481, No. 2481, pp. 203-217, December 2005, discloses an adaptive execution method for a symmetric multi-processor and distributed, shared memory parallel system. The article suggests a technique for sequentially executing a certain parallel loop to improve performance when executing the parallel loop in parallel, through a performance prediction of when compiling and several experiential criteria cause performance degradation. However, such a technique also does not reflect structural characteristics of each processor of the parallel system at all, and thus it is not appropriate as a method for achieving higher performance in the multithreaded processor-based parallel system having a shared cache structure.